The present invention relates to digital equalisation of signals. It finds a major application in the field of radio communications.
The method is applicable when the received signal results from a superimposition of different signals, sent from the same transmitter and/or different transmitters, for which the responses of the transmission channels between transmitter and receiver have been determined beforehand. One of the major problems arising in this situation is to strike a compromise between performance of the equaliser and its complexity. A complete maximum likelihood estimation of all the symbols of the overlaid signals is theoretically possible, using the Viterbi algorithm for example (see G. D. Forney Jr.: xe2x80x9cThe Viterbi Algorithmxe2x80x9d, Proc. of the IEEE, Vol. 61, No. 3, March 1973, pages 268-278). However, as the impulse response of the channels becomes long or the number of overlaid signals is high, the exponential complexity of these methods makes them impractical.
Spread spectrum radio communications using code division multiple access (CDMA) illustrate this problem.
Let us assume that K synchronous logical channels, denoted here by an index k (1xe2x89xa6kxe2x89xa6K), share the same physical channel, i.e. use the same carrier frequency at the same time, and are differentiated by spreading sequences ck respectively assigned to them. Each channel is used to transmit a respective signal made up of successive sequences dk, or frames, of n symbols dpk (1xe2x89xa6pxe2x89xa6n). The symbols dpk have discrete values:binary (xc2x11) in the case of a BPSK modulation, quaternary (xc2x11xc2x1j) in the case of a QPSK modulation, . . .
Let us also assume that the spreading sequences ck have a rate Q times greater than that of the symbols dpk, Q being an integer representing a spreading factor (the extreme situation Q=1 corresponds to no spreading), and a periodicity equal to the period of a symbol. The complex-valued samples (generally xc2x11 or xc2x11xc2x1j) of the spreading sequences ck or xe2x80x9cchipsxe2x80x9d are written cqk (1xe2x89xa6qxe2x89xa6Q). The sequences ck are selected so as to be mutually orthogonal   (                    ∑                  q          =          1                Q            ⁢              xe2x80x83            ⁢                        c          q          k                ·                  c          q                      k            xe2x80x2                                =                  0        ⁢                  xe2x80x83                ⁢        where        ⁢                  xe2x80x83                ⁢        k            ≠              k        xe2x80x2              )
in order to make it easier to distinguish between the channels. However, the propagation conditions, particularly the multiple paths, do not generally preserve this orthogonality, particularly in the case of short spreading sequences.
After base band conversion, digitisation and adapted filtering, a vector Y of the received signal reflecting the symbols emitted over a frame period is expressed as follows:                     Y        =                              (                                                                                y                    1                                                                                                                    y                    2                                                                                                ⋮                                                                                                  y                    p                                                                                                ⋮                                                                                                  y                    L                                                                        )                    =                                                    ∑                                                      k                    □                                    =                  1                                K                            ⁢                              xe2x80x83                            ⁢                                                (                                                                                                              r                          1                          k                                                                                            0                                                                    0                                                                    ⋯                                                                    0                                                                                                                                      r                          2                          k                                                                                                                      r                          1                          k                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                                                                                              xe2x80x83                                                                                                                      r                          2                          k                                                                                            ⋰                                                                                              xe2x80x83                                                                                            ⋮                                                                                                            ⋮                                                                                              xe2x80x83                                                                                            ⋰                                                                                              xe2x80x83                                                                                                                      xe2x80x83                                                                                                                                                              xe2x80x83                                                                                            ⋮                                                                    ⋰                                                                    0                                                                    0                                                                                                                                      r                          W                          k                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                                                      r                          1                          k                                                                                            0                                                                                                            0                                                                                              r                          W                          k                                                                                                                      xe2x80x83                                                                                                                      r                          2                          k                                                                                                                      r                          1                          k                                                                                                                                    0                                                                    0                                                                                              xe2x80x83                                                                                                                      xe2x80x83                                                                                                                      r                          2                          k                                                                                                                                                              xe2x80x83                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                            ⋮                                                                                              xe2x80x83                                                                                                                                    ⋮                                                                                              xe2x80x83                                                                                            ⋰                                                                                              xe2x80x83                                                                                            ⋮                                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                                                      r                          W                          k                                                                                                                      xe2x80x83                                                                                                                                    0                                                                    0                                                                    ⋯                                                                    0                                                                                              r                          W                          k                                                                                                      )                                ⁢                                  (                                                                                                                                          c                            1                            k                                                    ·                                                      d                            1                            k                                                                                                                                                                                                                    c                            2                            k                                                    ·                                                      d                            1                            k                                                                                                                                                              ⋮                                                                                                                                                                  c                            Q                            k                                                    ·                                                      d                            1                            k                                                                                                                                                                                                                    c                            1                            k                                                    ·                                                      d                            2                            k                                                                                                                                                              ⋮                                                                                                                                                                  c                            q                            k                                                    ·                                                      d                            p                            k                                                                                                                                                              ⋮                                                                                                                                                                  c                            Q                            k                                                    ·                                                      d                            n                            k                                                                                                                                )                                                      +                          Y              N                                                          (        1        )            
where W is the length, in number of chips, of the estimated impulse response of the channels, rk=(r1k, . . . , rwk) is the estimated impulse response of the k-th channel, the rjk being complex numbers such that rjk=0 if jxe2x89xa60 or j greater than W, yp is the p-th complex sample received (at the chip frequency) where 1xe2x89xa6pxe2x89xa6L=nQ+Wxe2x88x921, and YN is a vector of size L made up of additive noise samples. The estimated impulse response rk takes account of the propagation channel, shaping of the signal by the transmitter and filtering on reception.
The size of the problem can be reduced by a factor Q by integrating the codes ck in the responses rk, i.e. by calculating the following convolution products for 1xe2x89xa6jxe2x89xa6Lxe2x80x2=Q+Wxe2x88x921:                               b          j          k                =                              ∑                          q              =              1                        Q                    ⁢                      xe2x80x83                    ⁢                                    r                              j                +                1                -                q                            k                        ·                          c              q              k                                                          (        2        )            
Expression (1) then becomes:                     Y        =                                                            ∑                                  k                  =                  1                                K                            ⁢                              xe2x80x83                            ⁢                                                (                                                                                                              b                          1                          k                                                                                            0                                                                    ⋯                                                                    0                                                                                                            ⋮                                                                    ⋮                                                                                              xe2x80x83                                                                                                                      xe2x80x83                                                                                                                                                              b                          Q                          k                                                                                            0                                                                                              xe2x80x83                                                                                                                      xe2x80x83                                                                                                                                                              b                                                      Q                            +                            1                                                    k                                                                                                                      b                          1                          k                                                                                                                      xe2x80x83                                                                                            ⋮                                                                                                                                      xe2x80x83                                                                                            ⋮                                                                                              xe2x80x83                                                                                                                      xe2x80x83                                                                                                                                    ⋮                                                                                              b                          Q                          k                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                                                                                              xe2x80x83                                                                                                                      b                                                      Q                            +                            1                                                    k                                                                                            ⋰                                                                    0                                                                                                                                      b                                                      Q                            +                            W                            -                            1                                                    k                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                                                      b                          1                          k                                                                                                                                    0                                                                    ⋮                                                                                              xe2x80x83                                                                                                                                                  xe2x80x83                                                    ⁢                          ⋮                                                                                                                                                              xe2x80x83                                                                                                                      xe2x80x83                                                                                                                      xe2x80x83                                                                                                                      b                          Q                          k                                                                                                                                                              xe2x80x83                                                                                                                      b                                                      Q                            +                            W                            -                            1                                                    k                                                                                                                      xe2x80x83                                                                                                                      b                                                      Q                            +                            1                                                    k                                                                                                                                    ⋮                                                                    0                                                                                              xe2x80x83                                                                                                                      xe2x80x83                                                                                                                                                              xe2x80x83                                                                                                                      xe2x80x83                                                                                            ⋰                                                                    ⋮                                                                                                            0                                                                    ⋯                                                                    0                                                                                              b                                                      Q                            +                            W                            -                            1                                                    k                                                                                                      )                                ⁢                                  (                                                                                                              d                          1                          k                                                                                                                                                              d                          2                          k                                                                                                                                    ⋮                                                                                                                                      d                          n                          k                                                                                                      )                                                      +                          Y              N                                =                                                    ∑                                  k                  =                  1                                K                            ⁢                                                B                  k                                ·                                  D                  k                                                      +                          Y              N                                                          (        3        )            
The matrices Bk of size Lxc3x97n have a structure of the Toeplitz type along a diagonal having a slope Q (along the main diagonal if Q=1), i.e. if xcex2i,jK denotes the term located on the i-th row and j-th column of a matrix Bk, then xcex2ki+Q,j+1=xcex2i,jk where 1xe2x89xa6ixe2x89xa6Lxe2x88x92Q and 1xe2x89xa6jxe2x89xa6nxe2x88x921. The terms of the matrix Bk are given by: xcex21,jk=0 where 1xe2x89xa6jxe2x89xa6n (Bk therefore has only zeros above its main diagonal, and even above its diagonal of slope Q); xcex2i,1k=0 where Q+Wxe2x89xa6ixe2x89xa6L (band-matrix structure); and xcex2i,1k=bik where 1xe2x89xa6i less than Q+W.
In simple equalisers, the aim is merely to estimate the contribution of one channel, the contributions of the other channels being assimilated with noise. In other words, the receiver considers that K=1 after having determined the relevant response B1. The linear system (3) reduces to Y=B1D1+YN and can then be processed, using a method such as the Viterbi algorithm, which maximises the likelihood of the symbol estimations D1, using an equaliser of reasonable complexity provided the length W of the channel response is not too big.
If the contributions of several channels have to be estimated, one option is to use several simple equalisers of the type described above, operating in parallel with the responses of different channels. Obviously, however, it is preferable to resolve the system (3) in one go where K greater than 1 by trying to maximise the likelihood of the symbol estimates dpk as far as possible. This is referred to as joint equalisation.
A matrix A of L=nQ+Wxe2x88x921 rows and N=nQ columns and a vector D of N discrete components are defined in order to express the vector Y in the form:
Y=AD+YNxe2x80x83xe2x80x83(4)
One possible way of expressing the matrix and the vector D is as follows                               A          =                      (                                                                                B                    K                                                                    ⋯                                                                      B                    2                                                                                        B                    1                                                                        )                          ,                  xe2x80x83                ⁢                              and            ⁢                          xe2x80x83                        ⁢            D                    =                      (                                                                                D                    K                                                                                                ⋮                                                                                                  D                    2                                                                                                                    D                    1                                                                        )                                              (        5        )            
In this organisation of the matrix A and vector D, the components are arranged channel by channel.
The matrix A and vector D of the linear system (4) can also be organised so that the components are arranged symbol by symbol. The matrix A will then have a blockwise Toeplitz structure, with a same block B of Lxe2x80x2=Q+Wxe2x88x921 rows and K columns repeated n times with a offset of Q zero lines between adjacent blocks B, and the vector D is divided into corresponding blocks Di of a size K (1xe2x89xa6ixe2x89xa6n), i.e.                               where          ⁢                      xe2x80x83                    ⁢          B                =                                            (                                                                                          b                      1                      1                                                                                                  b                      1                      2                                                                            ⋯                                                                              b                      1                      k                                                                                                                                  b                      2                      1                                                                                                  b                      2                      2                                                                            ⋯                                                                              b                      2                      k                                                                                                            ⋮                                                        ⋮                                                                              xe2x80x83                                                                            ⋮                                                                                                              b                                              Q                        +                        W                        -                        1                                            1                                                                                                  b                                              Q                        +                        W                        -                        1                                            2                                                                            ⋯                                                                              b                                              Q                        +                        W                        -                        1                                            K                                                                                  )                        ⁢                          xe2x80x83                        ⁢            and            ⁢                          xe2x80x83                        ⁢                          D              i                                =                      (                                                                                d                    i                    1                                                                                                                    d                    i                    2                                                                                                ⋮                                                                                                  d                    i                    K                                                                        )                                              (        7        )            
One conventional solution for resolving a system such as (4) is the least square method, by means of which the vector {circumflex over (D)} is determined with N continuous components, which minimises the quadratic error xcex5=∥A{circumflex over (D)}xe2x88x92Y∥2. Discrete values of the components of the vector {circumflex over (D)} relating to each channel are then obtained, often through a channel decoder. The solution {circumflex over (D)} within the least square meaning is given by: {circumflex over (D)}=(AHA)xe2x88x921AHY, where AH denotes the conjugated transposed matrix of A. The problem is then reduced to inverting the positive defined Hermitian matrix AHA. This inversion may be performed by means of various conventional algorithms directly (Gauss, Cholesky, . . . methods) or using iterative methods (Gauss-Seidel algorithms, gradient algorithms . . . ).
The estimation error Dxe2x88x92{circumflex over (D)} is equal to (AHA)xe2x88x921AHYN, which demonstrates that the solution obtained is affected by a noise of variance:
"sgr"2=E(∥Dxe2x88x92{circumflex over (D)}∥2)=N0x Trace[(AHA)xe2x88x921]xe2x80x83xe2x80x83(8)
where N0 is the power spectral density of the noise. The noise is seen to be amplified if the matrix AHA is badly conditioned, i.e. when it has one or more eigenvalues close to 0.
This noise amplification is the main disadvantage of conventional resolution methods. In practice, the situations in which the matrix AHA is poorly conditioned arise frequently, especially in the presence of multiple propagation paths.
A relatively simple means is known of remedying this drawback to a certain extent by incorporating an interference residue in the solution, i.e. rather than using the optimum solution within the meaning of the least squares, by adopting instead the solution: {circumflex over (D)}MMSE=(AHA+{circumflex over (N)}0)xe2x88x921AHY, where {circumflex over (N)}0 denotes an estimation of the noise spectral density, which the receiver must therefore compute. This method is known as MMSE (minimum mean square error). It allows the estimation variance to be reduced by introducing a bias.
An object of this invention is to alleviate the above-mentioned limitation of the known joint equalisation methods and to propose a sound compromise between the estimation reliability and the complexity of the equaliser.
Accordingly, the invention proposes a digital equalisation method for estimating, from a vector Y of L digital samples of a received signal, the discrete symbols of at least one transmitted signal forming part of the components of a vector D of a size N, wherein the vector Y may be decomposed as Y=AD+YN, where A is a matrix of L rows and N columns, determined beforehand from measurements of the response of at least one transmission channel, and YN represents a vector of L noise samples. This method comprises the steps of:
determining an upper triangular matrix T of N rows and N columns and a vector Z of a size N such that the quadratic criteria ∥TXxe2x88x92Z∥2 and ∥AXxe2x88x92Y∥2 are minimum for the same vector X of size N;
dividing the vector Z into J blocks Zi (1xe2x89xa6ixe2x89xa6J) and the matrix T into J(J+1)/2 blocks Ti,j (1xe2x89xa6jxe2x89xa6ixe2x89xa6J), J being an integer greater than 1, the block Zi being made up of Ni components of the vector Z, where                     ∑                  i          =          1                J            ⁢              xe2x80x83            ⁢              N        i              =    N    ,
and the block Ti,j being made up of Ni rows and Nj columns, in the form: 
estimating N1 of the discrete symbols as being the components of a vector {circumflex over (D)}1 equal to that of the vectors X1, made up of N1 components taking the different possible values of the discrete symbols, which minimises the quantity ∥T1,1X1xe2x88x92Z1∥2.
The method exploits a priori the knowledge that the unknown variables to be estimated (the symbols of the vector D) assume discrete values. Taking this information into account a priori makes it possible to overcome the possible singularities of the linear system (4) to a certain extent.
Making the problem triangular, i.e. passing from matrix A to the triangular matrix T in the quadratic criterion to be minimised, simplifies the search for the optimum to a large extent by exploring the different possible discrete values of the symbols.
Sub-dividing the triangular matrix T into blocks enables iterative processing to be applied in order to successively estimate the symbols by blocks of size Ni. The method may thus include the following step, performed successively for each of the values of i from i=2 to i=imax, the integer imax being such that 2xe2x89xa6imaxxe2x89xa6J:
estimating Ni of the discrete symbols, as being the components of a vector {circumflex over (D)}i equal to that of the vectors Xi, made up of Ni components taking the different possible values of the discrete symbols, which minimises the quantity             "LeftDoubleBracketingBar"                                    T                          i              ,              i                                ⁢                      X            i                          +                              ∑                          j              =              1                                      i              -              1                                ⁢                      xe2x80x83                    ⁢                                    T                              i                ,                j                                      ⁢                                          D                ^                            j                                      -                  Z          i                    "RightDoubleBracketingBar"        2    .
If the vectors X of size N are broken down into J blocks Xi of size Ni in a manner similar to the vector Z       (          X      =              (                                                            X                J                                                                        ⋮                                                                          X                1                                                    )              )    ,
and with the notations xcex51=∥T1,1X1xe2x88x92Z1∥2 and, for 2xe2x89xa6ixe2x89xa6J, xcex5i=∥Ti,iXixe2x88x92{tilde over (Z)}i∥2 where                     Z        ~            i        =                  Z        i            -                        ∑                      j            =            1                                i            -            1                          ⁢                  xe2x80x83                ⁢                              T                          i              ,              j                                ⁢                      X            j                                ,
the global quadratic criterion to be minimised is             "LeftDoubleBracketingBar"              TX        -        Z            "RightDoubleBracketingBar"        2    =            ∑              i        =        1            J        ⁢          xe2x80x83        ⁢                  ϵ        i            .      
Applying the minimisation block by block (i.e. by calculating {circumflex over (D)}1 as the X1 with discrete values which minimise xcex51, then {circumflex over (D)}2 as the X2 with discrete values which minimise xcex52 where X1={circumflex over (D)}1 in the expression of {tilde over (Z)}2, then {circumflex over (D)}3 as the X3 with discrete values which minimise xcex53 where X1={circumflex over (D)}1 and X2={circumflex over (D)}2 in the expression of {tilde over (Z)}3, etc.) will certainly not lead to the optimum discrete solution {circumflex over (D)} as a general rule, but the solution is very close to the optimal one and the complexity for solving the system is decreased very considerably.
The linear system is completely resolved if imax=J. It is also possible to perform a smaller number of iterations (at the limit one only), for example if the receiver needs to estimate the transmitted signals on only some of the channels. This being the case, the algebraic process leading from the matrix A to the matrix T enables characteristics of the response from other channels to be taken into account to a certain extent, which can procure a gain in the likelihood of the estimations.
In the method proposed by the invention as outlined above, each iteration leads to determination of a single vector {circumflex over (D)}i. Since the solution obtained is generally sub-optimum, performance can be improved by retaining several candidate vectors for each iteration (on the basis of the discrete vectors for which the criterion xcex5i assumes the lowest values) and by selecting at the end of the loop the set of candidate vectors that will have minimised the global criteria. In this alternative embodiment, after having determined the matrix T and the vector Z and having divided them into blocks, the following step is performed successively for each of the values of i from i=1 to i=imax, the integer imax being such that 2xe2x89xa6imaxxe2x89xa6J:
determining a number Mixe2x89xa71 of estimation vectors Êi(m), (1xe2x89xa6mxe2x89xa6Mi), made up of       P    i    =            ∑              j        =        1            i        ⁢          xe2x80x83        ⁢          N      j      
components whose values are among the different possible values of the discrete symbols, in the form                     E        ^            i              (        m        )              =          (                        X          i                      (            m            )                                                E            ^                                i            -            1                                (                          m              xe2x80x2                        )                              )        ,
where Êixe2x88x921(mxe2x80x2) is an estimation vector of size Pixe2x88x921 determined at the preceding step if i greater than 1 (1xe2x89xa6mxe2x89xa6Mixe2x88x921) and Xi(m) is a vector of size Ni, whereby said Mi estimation vectors Êi(m) minimise the quantity:
xcex4i(m)=xcex4ixe2x88x921(mxe2x80x2)+∥Ti,iXi(m)xe2x88x92{tilde over (Z)}i(mxe2x80x2)∥2xe2x80x83xe2x80x83(10)
where xcex40(mxe2x80x2)=0, {tilde over (Z)}1(mxe2x80x2)=Z1, and, for i greater than 1:
{tilde over (Z)}i(mxe2x80x2)=Zixe2x88x92(Ti,ixe2x88x921¦. . . ¦Ti,2¦Ti,1)Êixe2x88x921(mxe2x80x2)xe2x80x83xe2x80x83(11)
The number Mimax being equal to 1, Pimax discrete symbols are then estimated by the components of the estimation vector Êimax(1).
Another aspect of the present invention relates to a radio communication receiver comprising conversion means for producing successive vectors Y of L digital samples from a received radio signal, means for measuring the response of at least one transmission channel, so as to determine, for each of said vectors Y, a matrix A of L rows and N columns such that the vector Y can be decomposed as Y=AD+YN, where D is a vector of size N made up of discrete symbols of at least one signal transmitted and YN represents a vector of L noise samples, and equalisation means implementing the above-defined digital equalisation method for estimating, on the basis of each vector Y, the discrete symbols of at least one transmitted signal forming part of the components of the corresponding vector D.